# -*- coding:utf-8 -*-
# AudibleAlgos
# Vincent Foley-Bourgon - vfoley <at> gmail <dot> com

import time
import random
import itertools


def MergeSort(xs):
    def merge(dst, left, right, lo, hi):
        i, j, k = 0, 0 , 0
        m, n = len(left), len(right)
        while i < m and j < n:
            if left[i] <= right[j]:
                dst[k] = left[i]
                i += 1
            else:
                dst[k] = right[j]
                j += 1
            k += 1

        while i < m:
            dst[k] = left[i]
            i += 1
            k += 1

        while j < n:
            dst[k] = right[j]
            j += 1
            k += 1

        for i, x in enumerate(dst):
            yield [lo+i]
            xs[lo+i] = x


    def mergesort_aux(ys, lo, hi):
        # lo and hi are only used to track which elements in the original
        # array are actually being manipulated.
        if len(ys) > 1:
            mid = len(ys) / 2
            left = ys[:mid]
            right = ys[mid:]
            a = mergesort_aux(left, lo, lo+mid-1)
            b = mergesort_aux(right, lo+mid, hi)
            c = merge(ys, left, right, lo, hi)
            return itertools.chain(a, b, c)
        else:
            return iter([])

    return mergesort_aux(xs, 0, len(xs)-1)

def SelectionSort(xs):
    for i in xrange(len(xs)-1, 0, -1):
        max = 0
        for j in xrange(1, i+1):
            yield [j, max]
            if xs[j] > xs[max]:
                max = j
        yield [i, max]
        xs[i], xs[max] = xs[max], xs[i]



def BubbleSort(xs):
    for i in xrange(len(xs)-1, 0, -1):
        for j in xrange(i):
            yield [j, j+1]
            if xs[j] > xs[j+1]:
                yield [j, j+1]
                xs[j], xs[j+1] = xs[j+1], xs[j]


def InsertionSort(xs):
    for i in xrange(1, len(xs)):
        j = i-1
        while j >= 0 and xs[j] > xs[j+1]:
            yield [j, j+1]
            xs[j], xs[j+1] = xs[j+1], xs[j]
            j -= 1



# This is a hack; since we can't use a return statement inside a
# generator (function using yield), this exception is used in
# quick sort's partition routine to exit and return the position
# of the pivot to the caller.
class PartitionExit(Exception):
    def __init__(self, pos):
        self.pos = pos

def QuickSort(xs):
    def partition(start, length, pivot_pos):
        pivot = xs[pivot_pos]
        yield [start, pivot_pos]
        xs[start], xs[pivot_pos] = xs[pivot_pos], xs[start]
        lo = start+1
        hi = start+length-1

        while lo < hi:
            while lo < hi and xs[lo] <= pivot:
                yield [start, lo, hi]
                lo += 1
            while lo < hi and xs[hi] >  pivot:
                yield [start, lo, hi]
                hi -= 1
            yield [start, lo, hi]
            xs[lo], xs[hi] = xs[hi], xs[lo]
        if xs[lo] > pivot: lo -= 1
        yield [start, lo]
        xs[start], xs[lo] = xs[lo], xs[start]
        raise PartitionExit(lo)

    def quicksort_aux(start, length):
        if length > 1:
            pivot_pos = start + random.randrange(length)
            try:
                for t in partition(start, length, pivot_pos):
                    yield t
            except PartitionExit as e:
                a = quicksort_aux(start, e.pos - start)
                b = quicksort_aux(e.pos+1, start+length-e.pos-1)
                for t in itertools.chain(a, b):
                    yield t

    return quicksort_aux(0, len(xs))


# http://en.wikipedia.org/wiki/Gnome_sort
def GnomeSort(xs):
    i = 1
    while i < len(xs):
        yield [i, i-1]
        if xs[i] >= xs[i-1]:
            i += 1
        else:
            xs[i], xs[i-1] = xs[i-1], xs[i]
            if i > 1:
                i -= 1
